package com.data.bobostructure.chapter2;
/**
 * Created by wangbing on 2018/3/30.
 */


import com.data.bobostructure.utils.SortUtils;

import java.util.Arrays;

/**
 * 自底向下进行排序
 */
public class MergeSortion03 {
    //    将arr[l,mid]和merge
    private static  void merge(Comparable arr[],int l,int mid,int r){
//        临时空间的生成
        Comparable[] aux = Arrays.copyOfRange(arr,l,r+1);
        for (int i=l;i<=r;i++){
            aux[i-l]= arr[i];
        }

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l;
        int j = mid+1;



        for (int k = l;k<=r;k++){
            /**
             * 数组越界问题:
             * 当归并开始时，如果有一方率先完成了排序，那么另一方就按照顺序，往剩余位置填充即可
             */
//        右边排好序了

            if (i>mid){
                arr[k] = aux[j-l];
                j++;
            }

            else if (j>r){
                arr[k] = aux[i-l];
                i++;
            }
// 常规操作
            // 左半部分所指元素 < 右半部分所指元素
            else if (aux[i-l].compareTo(aux[j-l])<0){
                arr[k] = arr[i+1];
                i++;

            }else {
                // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = arr[j-1];
                j++;
            }
        }



    }

    private static void mergeSortBU(Comparable[] arr){
        int len = arr.length;

        for (int size=1;size<=len;size+=size){


            for (int i=0;i+size<len;i+=size+size){
                 merge(arr,i,i+size-1,min(i+size+size-1,len-1));
            }
        }


    }

    private static int min(int i, int j) {
        return i>j?j:i;
    }
    public static void sort(Comparable[] arr){
        mergeSortBU(arr);
    }

    public static void main(String[] args) {
        int N = 1000000;
        Integer[] arr = SortUtils.generateRandomArray(N, 0, 100000);
        SortUtils.testSort("com.data.structure.chapter2.MergeSortion03","sort", arr);

    }
}
